#include <stdio.h>
#include <stdlib.h>

// 定义并查集结构体
typedef struct {
    int *parent;  // 父节点数组
    int *rank;    // 秩数组，用于按秩合并
    int size;     // 集合的大小
} DisjointSet;

// 创建并查集
DisjointSet* createSet(int size) {
    DisjointSet *set = (DisjointSet *)malloc(sizeof(DisjointSet));
    set->parent = (int *)malloc(size * sizeof(int));
    set->rank = (int *)malloc(size * sizeof(int));
    set->size = size;

    // 初始化父节点和秩
    for (int i = 0; i < size; i++) {
        set->parent[i] = i;
        set->rank[i] = 0;
    }

    return set;
}

// 查找根节点，并进行路径压缩
int find(DisjointSet *set, int x) {
    if (set->parent[x] != x) {
        set->parent[x] = find(set, set->parent[x]); // 路径压缩
    }
    return set->parent[x];
}

// 合并两个集合
void unionSets(DisjointSet *set, int x, int y) {
    int rootX = find(set, x);
    int rootY = find(set, y);

    if (rootX != rootY) {
        // 按秩合并
        if (set->rank[rootX] > set->rank[rootY]) {
            set->parent[rootY] = rootX;
        } else if (set->rank[rootX] < set->rank[rootY]) {
            set->parent[rootX] = rootY;
        } else {
            set->parent[rootY] = rootX;
            set->rank[rootX]++;
        }
    }
}

// 打印并查集中的每个元素的根节点
void printSets(DisjointSet *set) {
    for (int i = 0; i < set->size; i++) {
        printf("Element %d -> Root %d\n", i, find(set, i));
    }
}

// 释放并查集内存
void freeSet(DisjointSet *set) {
    free(set->parent);
    free(set->rank);
    free(set);
}

// 主函数示例
int main() {
    int size = 10;
    DisjointSet *set = createSet(size);

    // 合并操作
    unionSets(set, 1, 2);
    unionSets(set, 2, 3);
    unionSets(set, 4, 5);
    unionSets(set, 5, 6);
    unionSets(set, 7, 8);
    unionSets(set, 8, 9);

    // 打印集合
    printSets(set);

    // 释放内存
    freeSet(set);

    return 0;
}
